#ifndef _SORTING_ALGORITHMS_C
#define _SORTING_ALGORITHMS_C

void
Selection_sort(int* a, int n)
{
	register int i, k, min_k, tmp;

	for (i = 0 ; i < n - 1 ; ++i) {
		min_k = i+1;
		for (k = i + 1 ; k < n ; ++k) {
			if (a[k] < a[min_k]) {
				min_k = k;
			}
		}

		tmp      = a[i];
		a[i]     = a[min_k];
		a[min_k] = tmp;
	}
}


void
Insertion_sort(int* a, int n)
{
	register int i, k, tmp;

	for (i = 1 ; i < n ; ++i) {
		k = i;
		tmp = a[i];
		while (tmp < a[k-1] && k > 0) {
			a[k] = a[k-1];
			--k;
		}
		a[k] = tmp;
	}
}


void
Bubble_sort(int* a, int n)
{
	register int i, j, tmp;
	char F = false;

	for (i = 0; i < n; ++i) {
		for (j = 1; j < n - i; ++j) {
			if (a[j] < a[j-1]) {
				tmp = a[j];
				a[j] = a[j-1];
				a[j-1] = tmp;
				F = true;
			}
		}
		if (!F)
			break;
		F = false;
	}
}


/* {{{ Merge (recursive) */
void
Merge(int* a, int L, int M, int R)
{
	register int i = L,
		     j = M+1,
		     s = 0; /* index. points to where we will place next element */
	int sorted[NMAX];

	while (i <= M || j <= R) {
		if (a[i] < a[j]) {
			if 	(i <= M)
				sorted[s++] = a[i++];
			else if (j <= R)
				sorted[s++] = a[j++];
		} else {
			if 	(j <= R)
				sorted[s++] = a[j++];
			else if (i <= M)
				sorted[s++] = a[i++];
		}
	}

	i = 0;
	while (i < s) {
		a[L + i] = sorted[i];
		++i;
	}
}



void
Merge_sort(int* a, int L, int R)
{
	int M;
	if (L < R) {
		M = (L + R) / 2;

		Merge_sort(a, L, M);
		Merge_sort(a, M+1, R);

		Merge(a, L, M, R);
	}
}
/* }}} */


/* {{{ qsort_wtf */
void
my_qsort_wtf(long long int *array, long long L, long long R)
{
	long long tmp, x = *(array + (L+R) / 2);
	long long i = L, j = R;

	do {
		while ( *(array + i) < x )
			++i;
		while ( *(array + j) > x )
			--j;
		if (i <= j) {
			tmp = *(array + i);
			*(array + i) = *(array + j);
			*(array + j) = tmp;
			++i;
			--j;
		}
	} while (i <= j);

	if (L < j)
		my_qsort_wtf(array, L, j);
	if (i < R)
		my_qsort_wtf(array, i, R);
}
/* }}} */


/* {{{ Heap sort */
void
swap_ints(int* a, int* b)
{
	int T;
	T  = *a;
	*a = *b;
	*b =  T;
}



void
Heap_sort__sift_down(int * array, int start, int end)
{
	int parent = start,
	    child,
	    swap;

	while (parent * 2 + 1 <= end) {
		child = parent * 2 + 1;
		swap = parent;

		if (array[swap] < array[child])
			swap = child;

		if (child+1 <= end && array[swap] < array[child+1])
			swap = child+1;

		if (swap != parent) {
			swap_ints(&array[parent], &array[swap]);
			parent = swap;
		} else {
			return;
		}
	}
}



void
Heap_sort__sift_up(int * array, int start, int end)
{
	int child = end,
	    parent = (end - 1) / 2;

	/*
	 * 'start' is a kind of left barrier for this function
	 */
        while (child > start) {
		if (array[(child - 1) / 2] < array[child]) {
			swap_ints(&array[parent], &array[child]);

			child  = parent--;
			parent /= 2;
		} else
			return;
	}
}



void
Heap_sort__heapify(int* array, int size)
{
	int start = size / 2 - 1;

	while (start >= 0) {
		Heap_sort__sift_down(array, start--, size - 1);
	}
}



void
Heap_sort(int *array, int size)
{
	int end = size - 1;

	Heap_sort__heapify(array, size);

	while (end > 0) {
		swap_ints(&array[end], &array[0]);

		Heap_sort__sift_down(array, 0, --end);
	}
}
/* }}} */


void
Shell_sort(int* array, int n);


/* {{{ Quick sort */
int
Quick_sort__partition(int * array, int L, int R)
{
	int p = array[(rand() % (R-L)) + L];
	register int i = L, j = R;
	while (i <= j) {
		while (array[i] < p)
			++i;
		while (array[j] > p)
			--j;
		if (i < j) {
			swap_ints(&array[i], &array[j]);
			++i;
			--j;
		} else
			return j;
	}
	return j;
}



void
Quick_sort__main(int *array, int left, int right)
{
	int m;

	if (left < right) {
		m = Quick_sort__partition(array, left, right);
		Quick_sort__main(array, left, m);
		Quick_sort__main(array, m+1, right);
	}
	return;
}



void
Quick_sort(int * array, int size)
{
	return Quick_sort__main(array, 0, size-1);
}
/* }}} */


#endif /* #ifndef _SORTING_ALGORITHMS_C */
// vim: foldmethod=marker:
